package cn.bellychang.leetcode.question875;

import java.util.Arrays;

/**
 *
 * Koko loves to eat bananas.  There are N piles of bananas, the i-th pile has piles[i] bananas.
 * The guards have gone and will come back in H hours.
 *
 * Koko can decide her bananas-per-hour eating speed of K.
 * Each hour, she chooses some pile of bananas, and eats K bananas from that pile.
 * If the pile has less than K bananas, she eats all of them instead, and won't eat any more bananas during this hour.
 *
 * Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.
 *
 * Return the minimum integer K such that she can eat all the bananas within H hours.
 *
 * @author ChangLiang
 * @date 2021/2/3
 */
public class Solution {

    public int minEatingSpeed(int[] piles, int H) {
        int speedL = 1;
        int speedR = Arrays.stream(piles).max().getAsInt();
        while (speedL < speedR) {
            int middle = (speedR - speedL) / 2 + speedL;
            if (getHours(piles,middle) > H) {
                // middle太小了
                speedL = middle + 1;
            } else {
                speedR = middle;
            }
        }
        return speedL;
    }

    public int getHours(int[] piles, int speed) {
        int hours = 0;

        for (int i = 0; i < piles.length; i++) {
            hours += (piles[i] / speed + (piles[i] % speed == 0 ? 0 : 1));
        }
        return hours;
    }
}
